package offer;

/**
 * @Author Elephas
 * @Date 2022/1/16
 **/
public class AddTwoNumbers {
    public static void main(String[] args) {
        final ListNode TEST01_L1 = ListNode.ListNode(new int[]{2,4,3});
        final ListNode TEST01_L2 = ListNode.ListNode(new int[]{5,6,4});
        final ListNode TEST02_L1 = ListNode.ListNode(new int[]{9,9,9,9,9,9});
        final ListNode TEST02_L2 = ListNode.ListNode(new int[]{9,9,9,9});
        final ListNode TEST03_L1 = ListNode.ListNode(new int[]{2,4,9});
        final ListNode TEST03_L2 = ListNode.ListNode(new int[]{5,6,4,9});

        addTwoNumbers(TEST03_L1,TEST03_L2);

    }

    /*
        将两个链表对应相加，可能产生进位
        算法思路：先将两个链表逆序，对应相加决定进位
     */

    public static ListNode addTwoNumbers(ListNode l1, ListNode l2){
        ListNode p1 = l1,p2 = l2;
        boolean C = false;
        // 补0，使得两个链表对齐
        if( p1 == null){
            return l2;
        }else if( p2 == null){
            return l1;
        }
        while(p1.next != null || p2.next != null){
            if(p1.next != null && p2.next == null){
                p2.next = new ListNode(0,null);
            }else if( p1.next == null && p2.next != null){
                p1.next = new ListNode(0,null);
            }
            p1 = p1.next;
            p2 = p2.next;
        }
        p1 = l1;p2 = l2;

        while( p1 != null && p2 != null){
            if(!C){
                if(p1.val + p2.val >= 10){
                    C = true;
                    p1.val = p1.val + p2.val - 10;
                }else{
                    C = false;
                    p1.val = p1.val + p2.val;
                }
            }else{
                if(p1.val + p2.val + 1 >= 10){
                    C = true;
                    p1.val = p1.val + p2.val +1 - 10;
                }else{
                    C = false;
                    p1.val = p1.val + p2.val + 1;
                }
            }
            p1 = p1.next;
            p2 = p2.next;
        }
        if( !C ){
            return (l1);
        }else{
            p1 = l1;
            while(p1.next != null){
                p1 = p1.next;
            }
            p1.next = new ListNode(1,null);
            return l1;
        }

    }
    public static ListNode reverse(ListNode head){
        ListNode fakeHead = new ListNode(0);
        ListNode cur;
        while(head != null){
            cur = head;
            head = head.next;
            cur.next = fakeHead.next;
            fakeHead.next = cur;
        }
        return fakeHead.next;
    }
}
